import java.util.Arrays;
import java.util.Stack;

public class Double_ListNode {

    static class ListNode_D {
        public int val;
        public ListNode_D next;
        public ListNode_D prev;

        public ListNode_D(int val) {
            this.val = val;
        }

    }

    public ListNode_D head;//头节点
    public ListNode_D end;//尾节点

    public void addFirst(int val) {
        ListNode_D cur = new ListNode_D(val);
        if (head == null) {
            head = cur;
            end = cur;
            return;
        }
        cur.next = head;
        head.prev = cur;
        head = cur;
    }

    //在指定数字后面插入 val
    public void addIndex(int index, int val) {
        ListNode_D cur = getNode(index);
        if (cur == null) {
            return;
        }
        if (cur == end) {
            addLast(val);
            return;
        }
        ListNode_D add_cur = new ListNode_D(val);
        add_cur.prev = cur;
        add_cur.next = cur.next;
        cur.next.prev = add_cur;
        cur.next = add_cur;
    }
    public void addLast(int val) {
        ListNode_D cur = new ListNode_D(val);
        if (head == null) {
            addFirst(val);
            return;
        }
        end.next = cur;
        cur.prev = end;
        end = cur;
    }
    public void delHead() {//头删

        if (head != null) {
            head = head.next;
            head.prev = null;
        } else {
            delNode();
        }

    }
    public void delNode() {//尾删
        ListNode_D tmp = end;
        if (end == null) {
            return;
        }
        if (Count() == 1) {//只剩下一个
            end = null;
            head = null;
            return;
        }
        end = end.prev;
        tmp.prev.next = null;
    }
    public void delNode(int index) {//删除指定下标的元素
        ListNode_D cur = getNode(index);
        if (cur == null) {
            return;
        }
        if (cur == end) {//尾删
            delNode();
            return;
        }
        if (cur == head) {//头删{}
            head = head.next;
            head.prev = null;
            return;
        }
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
    }

    public ListNode_D valNode(int val) {//对应值
        ListNode_D tmp = head;
        while (tmp != null) {
            if (tmp.val == val) {
                return tmp;
            }
            tmp = tmp.next;
        }
        return null;
    }

    public void delNode(ListNode_D del) {//删除指定节点
        if (del == null) {
            return;
        }
        if (del == head) {
            delHead();
            return;
        }
        if (del == end) {
            delNode();
            return;
        }
        del.prev.next = del.next;
        del.next.prev = del.prev;
    }
    public void delAll(int target) {

        while (Contain(target)) {
            //找到这个节点
            ListNode_D tmp = valNode(target);
            //删除tmp
            delNode(tmp);
        }
}
    public void clear() {
        ListNode_D cur = head;
        while (cur != null) {
            ListNode_D curN = cur.next;
            cur.next = null;
            cur.prev = null;
            cur = curN;
        }
        head = end = null;
    }
    //改变指定下标下的值

    public void setVal(int index, int val) {
        ListNode_D tmp = getNode(index);
        if (tmp == null) {
            return;
        }
        tmp.val = val;
    }
    //对应下标
    public ListNode_D getNode(int index) {
        ListNode_D tmp = head;
        int count = index;
        if (count < 0 || count > Count()) {
            return null;
        }
        while (tmp != null ) {
            if (count == 0) {
                return tmp;
            }
            count--;
            tmp = tmp.next;
        }
        return null;
    }
    public void Display() {
        ListNode_D tmp = head;
        while (tmp != null) {
            System.out.print(tmp.val + " ");
            tmp = tmp.next;
        }
        System.out.println();
    }

    public int Count() {
        ListNode_D tmp = head;
        int count = 0;
        while (tmp != null) {
            tmp = tmp.next;
            count++;
        }
        return count;
    }

    public boolean Contain(int val) {
        ListNode_D tmp = head;
        while (tmp != null) {
            if (tmp.val == val) {
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }

    @Override
    public String toString() {
        StringBuilder h = new StringBuilder();
        ListNode_D tmp = head;
        h.append(" ");
        while (tmp != null) {
            h.append(tmp.val);
            h.append(" ");
            tmp = tmp.next;
        }
        String end = h.toString();
            return "Double_ListNode{" + end +'}';
    }
}

class wow {

    public static void main(String[] args) {
        Double_ListNode hh = new Double_ListNode();
        for (int i = 0; i < 5; i++) {
            hh.addLast(i);
        }
        hh.addLast(1);
        hh.addLast(1);
        hh.addLast(1);
        hh.addLast(0);
        hh.addLast(0);
        hh.addLast(0);
        hh.Display();
        hh.delAll(1);
        hh.delAll(0);
        hh.Display();
        System.out.println(hh);
        System.out.println("ss");
    }
    public static void main3(String[] args) {
        Double_ListNode hh = new Double_ListNode();
        for (int i = 0; i < 10; i++) {
            hh.addLast(i);
        }
        hh.Display();
        for (int i = 0; i < 10; i++) {
            hh.delNode();
        }
        hh.Display();
        for (int i = 0; i < 8; i++) {

            hh.delNode(i);
        }
        hh.Display();
        for (int i = 0; i < 8; i++) {

            hh.addLast(i);
        }
        hh.Display();
        hh.clear();
        hh.Display();
    }
    public static void main2(String[] args) {
        Double_ListNode hh = new Double_ListNode();
        for (int i = 0; i < 5; i++) {
            hh.addLast(i + 1);
        }
        hh.clear();
//        for (int i = 0; i < 10; i++) {
//            hh.delNode(0);
//            hh.Display();
//        }
        hh.Display();
//        hh.Display();
//        hh.delNode(1);
//        hh.Display();
//        hh.delNode(3);
//        hh.Display();
//        hh.delNode(0);
//        System.out.println(hh.getNode(0).val);
//        hh.Display();
    }

    public static void main1(String[] args) {
        Double_ListNode hh = new Double_ListNode();
        for (int i = 0; i < 5; i++) {
            hh.addFirst(i);
        }
        hh.Display();
        System.out.println(hh.Contain(3));
        System.out.println(hh.Contain(43));
        System.out.println(hh.Count());
        for (int i = 0; i < 5; i++) {
            hh.addLast(i);
        }
        hh.Display();
        hh.setVal(0, 333);
        hh.Display();
        hh.addIndex(0, 77755);
        hh.addIndex(1, 777);
        hh.addIndex(0, 777577);
        hh.Display();
        for (int i = 0; i < 150; i++) {
            hh.delNode();
        }
        hh.Display();
        System.out.println("meila");
//        Double_ListNode hhh = new Double_ListNode();
//        for (int i = 0; i < 5; i++) {
//            hhh.addLast(i);
//        }
//        hhh.Display();

    }
}